1. Field of the Invention
The invention relates to a stack machine, and more particularly, to a method and apparatus for folding a plurality of instructions.
2. Description of the related Art
Please refer to FIG. 1. FIG. 1 is a functional block diagram of a stack machine 10. The prior art of a stack machine is disclosed in Bulman, D. M., "Stack Computers: An Introduction," IEEE Computer, Vol. 10, No. 5, May 1977, p. 18.about.28. The prior art of a pipeline machine is disclosed in Harold S. Stone, "High-Performance Computer Architecture," Addison-Wesley Publishing Company, 1987, p.102.about.115. We can learn from the related art of the above materials that the modern stack machine 10 could comprise:
an instruction cache 41 for storing a plurality of instructions, PA1 an instruction ring buffer 42 for storing a predetermined number of the instructions, PA1 an operation code checker (sizer) 44 for determining the size of each instruction in the instruction ring buffer 42 based on an operation code, and obtaining indicators of the operation code and operands of the instruction for identifying the operation code and the operands such that indicators of operation codes are 1 and that of operands are 0, PA1 a program controller 60 for controlling access or shift of the instructions stored in the instruction cache 41 or the instruction ring buffer 42 according to the indicators of the instructions generated in the operation code checker 44, PA1 a decoder 52 for decoding each of the operation codes according to its instruction format, and outputting a control signal 109 for providing an execution unit 54 with an executable function such as addition, subtraction, multiplication, division and shifting, PA1 an address generation unit 55 for generating a source address 105 and a destination address 107, an executable instruction buffer 58 for storing the source address 105, the destination address 107, and the control signal 109, and PA1 an execution unit 54 for receiving the control signal 109, source address 105 and destination address 107 from the executable instruction buffer 58, and executing the control signal 109 such as addition, subtraction, multiplication, division and shifting by reading and storing data through a local variable register 18, operand stack 12 or constant register 16 according to the source and destination addresses 105, 107. PA1 Step 1: accessing data from a source such as the constant register 16 or local variable register 18 and storing it to top of the operand stack (TOS) 12 according to the producer 14 because data are accessed through the operand stack 12 in a first in last out manner; PA1 Step 2: reading the data from the top of the operand stack 12 (TOS); PA1 Step 3: having the execution unit 54 use the operator 20 to execute the data to obtain an executed data; PA1 Step 4: storing the executed data to the top of the operand stack (TOS) 12; PA1 Step 5: accessing the executed data from the top of the stack (TOS) 12 and storing it to the local variable register 18 according to the consumer 22.
Please refer to FIG. 2. FIG. 2 is an operation flow of the stack machine 10. Instructions can be classified into three basic types by the viewpoint of the present invention. They are producer (P) 14, operator (O) 20, and consumer (C) 22. Assuming three instructions in the sequence of type P, O, C are to be executed and the instruction of type O has to be stored into the operand stack 12 after execution, operations of the three instructions are as follows:
The above steps show that data have to be accessed through the operand stack 12. This is called data dependency and it causes the waste of operation time.
A related art method of speeding up operations of instructions is disclosed in U.S. Pat. No. 5,214,763. This method utilizes a super scalar technique to perform operations of instructions by using a plurality of function units. Although the instructions are operated at the same time, the problem of data dependency still persists. Moreover, the use of the function units will make operations of the instructions very complicated.